Atari Mega Archive 1/Atari Mega Archive - Volume 1.iso/program/progem.arc/gem5.asc

Text File | 1987-10-10 | 17KB | 335 lines

                        *PROFESSIONAL GEM*
                Part 5 -- Resource Tree Structures
                           By Tim Oren

     This is the fifth issue of ST PROFESSIONAL GEM, concluding our
trek through GEM dialogs and resources with a look at the internal
structure of object trees.  Also, I'll answer a number of questions
of general interest which have been received via the ANTIC ONLINE
FEEDBACK.  As always, there is a download file associated with this
column: GEMCL5.C, which you will find in DL3 of the new Atari 16-bit
SIG (type GO PCS-58 or GO ATARI16).

     Even if you have no immediate use for this issue's code, be sure
to take the download anyway; some of the routines will be used in
later articles.

     In the last installment, we established that resources trees are
pointed to by the tree index, and that they are composed of objects
which contain pointers onward to other structures.  However, we
passed over the issue of linkage among the objects within a tree.  It
is now time to go back and cure this omission.

     The technical term for the linkage scheme of an object tree is a
"right-threaded binary tree".   If you already know what this is, you
can skim over the next few paragraphs.  If you happen to have access
to a copy of the book "FUNDAMENTAL ALGORITHMS", which is part of the
series THE ART OF COMPUTER PROGRAMMING by Donald E. Knuth, you might
want to read his excellent discussion of binary trees beginning on
page 332.

     For the following discussion, you should have a listing of the C
image of a resource tree in front of you.  For those who do not have
the listing from the last column, I have included a fragment at the
beginning of the download.  Before we begin, I should warn you of one
peculiarity of "computer trees":  They grow upside-down!  That is,
when they are diagrammed or described, their root is at the top, and
the  "leaves" grow downward.  You will see this both in the listing,
and in the way the following discussion talks about moving through
trees.

     Each GEM object tree begins at its ROOT object, numbered zero,
which is the object pointed at by the tree index.  There are three
link  fields at the beginning of each object.  They are called
OB_NEXT, OB_HEAD,  and OB_TAIL, which is the order in which they
appear.

     Each of the links is shown as an index relative to the root of
the current tree.  This means that the link '0' would refer to the
root of the tree, while '2' would indicate the object two lines below
it. The special link -1 is called NIL, and means that there is no
link in  the given direction.

     Each object, or node, in a tree may have "offspring" or nodes
which are nested below it.  If it does, then its OB_HEAD will point
to its first (or "leftmost") "child", while the OB_TAIL will point to
the last ("rightmost") of its offspring.  The OB_NEXT pointer links
the  children together, with the OB_NEXT of the first pointing to the
second, and so on, until the OB_NEXT of the last finally points back
to its parent, the object at which we started.

     Remember that each of these children may in turn have offspring
of their own, so that the original "parent" may have a large and
complex collection of "descendents".

     Let's look at the first tree in the download to see an example
of this structure.  The very first object is the ROOT.  Note that its
OB_NEXT is NIL, meaning that there are no more objects in the tree:
the ROOT is both the beginning and the end of the tree.  In this
case, the OB_HEAD is 1 and the OB_TAIL is 3, showing that there are
at least two different children.

     Following OB_HEAD down to the next line, we can trace through
the OB_NEXT links (2, 3, 0) as they lead through a total of three
children and back to the ROOT.  You will notice that the first two
children have NIL for the OB_HEAD and OB_TAILs, indicating that they
have no further offspring.

     However, node three, the last child of the ROOT, does have the
value 4 for both its OB_HEAD and OB_TAIL.  By this we can tell that
it  has one, and only one, offspring.  Sure enough, when we look at
node four, we see that its OB_NEXT leads immediately back to node
three. Additionally, it has no further offspring because its OB_HEAD
and OB_TAIL are NIL.

     You will find that object trees are always written out by the
Resource Construction Set in "pre-order".  (Again, see Knuth if you
have a copy.)  This means that the ROOT is always written first, then
its offspring left to right.  This rule is applied recursively, that
is, we go down to the next level and write out each of these nodes,
then THEIR children left to right, and so on.

     For a further example, look at the next tree in rs_object in the
download.  You will see that the ROOT has an OB_HEAD of 1 and an
OB_TAIL of 6, but that it actually has only three offspring (nodes 1,
2 and 6).  We see that node 2 itself had children, and applying the
rule given above, they were written out before continuing with the
next child of the ROOT.

     Why was this seemingly complex structure chosen for GEM?  The
reason has do with the tasks of drawing objects in their proper
locations on the screen, and determining which object was "hit" when
a mouse click is detected.

     To find out how this works, we must look at four more fields
found in each object: OB_X, OB_Y, OB_WIDTH, and OB_HEIGHT.  These
fields are the last four on each line in the sample trees.

     Each object in a tree "owns" a rectangle on the screen.  These
fields define that rectangle.  When a resource is stored "outside"
the  program the fields are in character units, so that an object
with OB_WIDTH  of 10 and OB_HEIGHT of 2 (for instance) would define a
screen area 10  characters wide and 2 high.

     When the resource is read into memory with an rsrc_load call,
GEM multiplies the appropriate character dimension in pixels into
each of these fields.  In this way portability is achieved: the same
resource file works for any of the ST's three resolutions.  Knowing
how rsrc_load works, your code should treat these fields as pixel
coordinates.

     (I have committed one oversimplification above.  If an object is
not created on a character boundary in the RCS, then the external
storage method described will not work.  In this case, the lower byte
of each rectangle field is used to store the nearest character
position, while the upper byte stores the pixel remainder to be added
after the character size is multiplied in.

     Non-character-boundary objects may only be created in the "FREE"
tree mode of the Resource Construction Set (also called "PANEL" in
RCS 2.0). You should use them only in programs which will run in a
single ST screen  mode, because pixel coordinates are not portable
between resolutions.)

     The first real secret of object rectangles is that each OB_X and
OB_Y is specified RELATIVE to the X and Y coordinate of its parent
object  within the tree.  This is the first property we have seen
that is actually "inherited" from level to level within the tree.

     The second secret is more subtle:  Every object's rectangle must
be entirely contained within the rectangle of its parent.  This
principle goes by the names "bounding rectangles" or "visual
hierarchy".  We'll see in a moment how useful it is when detecting
mouse/object collisions.

                         HOW GEM DOES IT.

     Knowing these secrets, and the linkage structure  of object
trees, we can deduce how a number of the GEM operations must work.
For instance, consider objc_offset,  which returns the actual screen
X and Y  of an object.  We can see now that simply loading the OB_X
and OB_Y fields of  the object does not suffice: they only give the
offset relative to the parent  object.  So, objc_offset must BEGIN
with these values, and then work its way  back up to the ROOT of the
tree, adding in the offsets found at each level.

     This can be done by following the OB_NEXT links from the chosen
object.  Whenever OB_NEXT points to an object whose OB_TAIL points
right back  to the same location, then the new node is another level,
or "parent" in the  tree, and objc_offset adds its OB_X and OB_Y into
the ru